package 剑指offer;

import leetcode.editor.cn.MergeListNode;
import 抽象数据类型.ListNode;

/**
 * @description:
 * @author: ywk
 * @date: 2020-11-01
 */
public class 判断一个链表是否为回文结构 {
    public static void main(String[] args) {
        ListNode l1 = MergeListNode.proList(new int[]{-3, -1, 2, 9}, 0, null);
        System.out.println(isPail(l1));
    }

    /**
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    public static boolean isPail(ListNode head) {
        // write code here
        if (head == null) {
            return false;
        }
        ListNode temp = head;
        int count = 0;
        while (temp != null) {
            count++;
            temp = temp.next;
        }
        if (count == 0) {
            return true;
        }
        int mid = count / 2;
        int index = 0;
        ListNode curNode = head;
        while (index < mid) {
            int i = 0;
            ListNode indexNode = curNode;
            while (i < count-index-1) {
                i++;
                indexNode = indexNode.next;
            }
            if (indexNode.val != curNode.val) {
                return false;
            }
            index++;
            curNode = curNode.next;
        }
        return true;
    }
}
